﻿public class Solution
{

    private IList<string> result = new List<string>();
    public IList<string> FindItinerary(IList<IList<string>> tickets)
    {
        // 使用辅助字典
        Dictionary<string, SortedDictionary<string, int>> ticketsDictionary =
            new Dictionary<string, SortedDictionary<string, int>>();

        foreach (IList<string> ticket in tickets)
        {
            if (ticketsDictionary.ContainsKey(ticket[0]))
            {
                if (ticketsDictionary[ticket[0]].ContainsKey(ticket[1]))
                {
                    ticketsDictionary[ticket[0]][ticket[1]]++;
                }
                else
                {
                    ticketsDictionary[ticket[0]][ticket[1]] = 1;
                }
            }
            else
            {
                ticketsDictionary[ticket[0]] = new SortedDictionary<string, int>();
                ticketsDictionary[ticket[0]][ticket[1]] = 1;
            }
        }
        
        result.Add("JFK");
        trackbacking(ticketsDictionary, tickets.Count);
        // 初始化
        return result;
    }

    private bool trackbacking(Dictionary<string, SortedDictionary<string, int>> ticketsDictionary, int Count)
    {
        if (result.Count == Count + 1) return true;

        string cur = result[result.Count - 1];
        
        SortedDictionary<string, int> dic = ticketsDictionary[cur];
        IList<string> strList = dic.Keys.ToList();
        for(int i = 0; i < strList.Count; i++)
        {
            string str = strList[i];
            if (dic[str] > 0)
            {
                dic[str]--;
                result.Add(str);
                if (trackbacking(ticketsDictionary, Count)) return true;
                result.RemoveAt(result.Count-1);
                dic[str]++;
            }
        }
        return false;
    }

    public static void Main(string[] args)
    {
        IList<IList<string>> tickets = new List<IList<string>>()
        {
            new List<string>() { "JFK", "SFO" },
            new List<string>() { "JFK", "ATL" },
            new List<string>() { "SFO", "JFK" },
            new List<string>() { "ATL", "AAA" },
            new List<string>() { "AAA", "ATL" },
            new List<string>() { "ATL", "BBB" },
            new List<string>() { "BBB", "ATL" },
            new List<string>() { "ATL", "CCC" },
            new List<string>() { "CCC", "ATL" },
            new List<string>() { "ATL", "DDD" },
            new List<string>() { "DDD", "ATL" },
            new List<string>() { "ATL", "EEE" },
            new List<string>() { "EEE", "ATL" },
            new List<string>() { "ATL", "FFF" },
            new List<string>() { "FFF", "ATL" },
            new List<string>() { "ATL", "GGG" },
            new List<string>() { "GGG", "ATL" },
            new List<string>() { "ATL", "HHH" },
            new List<string>() { "HHH", "ATL" },
            new List<string>() { "ATL", "III" },
            new List<string>() { "III", "ATL" },
            new List<string>() { "ATL", "JJJ" },
            new List<string>() { "JJJ", "ATL" },
            new List<string>() { "ATL", "KKK" },
            new List<string>() { "KKK", "ATL" },
            new List<string>() { "ATL", "LLL" },
            new List<string>() { "LLL", "ATL" },
            new List<string>() { "ATL", "MMM" },
            new List<string>() { "MMM", "ATL" },
            new List<string>() { "ATL", "NNN" },
            new List<string>() { "NNN", "ATL" }
        };

        Solution solution = new Solution();
        IList<string> result = solution.FindItinerary(tickets);

        foreach (string str in result)
        {
            Console.Write($"{str} ");
        }
    }
}